#include<bits/stdc++.h>
using namespace std;



class Node {
public:
    int val;
    vector<Node*> children;

    Node() {}

    Node(int _val) {
        val = _val;
    }

    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};


// class Solution {
// public:
//     vector<int> postorder(Node* root) {
//         vector<int> temp;
//         if(!root)return temp;
//         if(root->children.size() == 0) temp.emplace_back(root->val);
//         else {
//             for(auto item : root->children){
//                 vector<int>back = postorder(item);
//                 temp.insert(temp.end(), back.begin(), back.end());
//             }
//         }
//         return temp;
//     }
// };
/**
 * @brief 2022.4.11
 * 递归，在调用函数返回 vector 时会反复赋值，导致时间很长
 */


// class Solution {
// public:

//     void fun(Node* root, vector<int>& ans){
//         for(auto item : root->children){
//             fun(item, ans);
//         }
//         ans.emplace_back(root->val);
//     }

//     vector<int> postorder(Node* root) {
//         vector<int> ans;
//         if(!root)return ans;
//         fun(root, ans);
//         return ans;
//     }
// };
/**
 * @brief 2022.4.11
 * 递归优化，省去了重复创建赋值 vector的时间
 */


// class Solution {
// public:
//     vector<int> postorder(Node* root) {
//         stack<pair<Node*, int>> st;
//         vector<int> ans;
//         if(!root)return ans;
//         st.push({root, 0});
//         while(!st.empty()){
//             Node *temp = st.top().first;
//             int i_temp = st.top().second;
//             st.pop();
//             if(i_temp == temp->children.size()){
//                 ans.push_back(temp->val);
//             }
//             else{
//                 st.push({temp, i_temp + 1});
//                 st.push({temp->children[i_temp], 0});
//             }
//         }
//         return ans;
//     }
// };
/**
 * @brief 迭代
 * 
 */


class Solution {
public:
    vector<int> postorder(Node* root) {
        stack<Node*> st;
        vector<int> ans;
        unordered_set<Node*> visited;
        if(!root)return ans;
        st.emplace(root);
        while(!st.empty()){
            Node *temp = st.top();
            if(temp->children.size() == 0 || visited.count(temp)){
                ans.emplace_back(temp->val);
                st.pop();
            } else {
                for(auto rit = temp->children.rbegin(); rit != temp->children.rend(); rit++){
                    st.push(*rit);
                }
                visited.emplace(temp);
            }
        }
        return ans;
    }
};
/**
 * @brief 迭代优化 
 * 当从栈中取出某节点时，如果该节点为叶子节点或者已被访问，则将其 val 加入 ans
 * 否则将其标记，将其孩子节点从右到左入栈
 */